package sort;

import java.util.Arrays;

/**
 * description:
 * author:张腾
 * date:2021-03-28
 */

/**
 * 快速排序  时间复杂度O(nlogn)
 * 首先设定一个分界值（默认取数组首位）
 * 将大于分界值的放到分界值右边，小于的放到左边
 * 将左右两边的子数组在重复以上操作 直到每个子数组都有序
 */
public class Quick {

    public static void main(String[] args) {
        int[] a = new int[]{3,1,7,4,5,6};
        Quick q = new Quick();
//        q.sort(a);
        System.out.println(q.quickSort(a, 0, a.length - 1));
        System.out.println(Arrays.toString(a));
    }

//    //比较v是否小于w ,true表示v<w
//    private static boolean less(Comparable v,Comparable w){
//        return v.compareTo(w) < 0;
//    }
//
//    //数组元素i和j交换位置
//    private static void exch(Comparable[] a,int i ,int j){
//        Comparable t = a[i];
//        a[i] = a[j];
//        a[j] = t;
//    }
//
//    //对数组内的元素进行排序
//    public static void sort(Comparable[] a){
//        int lo = 0;
//        int hi = a.length-1;
//        sort(a,lo,hi);
//    }
//
//    //对数组内从索引lo到hi之间的元素进行排序
//    public static void sort(Comparable[] a,int lo,int hi){
//        if (hi<=lo) return;
//        //对数组从索引lo到hi之间的元素进行分组
//        int partition = partition(a,lo,hi); //返回分组的分界值在位置变换后的索引
//
//        sort(a,lo,partition);
//        sort(a,partition+1,hi);
//    }
//
//    //对数组中从索引lo到hi之间的元素进行分组，并返回分组界限对应的索引
//    public static int partition(Comparable[] a,int lo,int hi){
//        //确定分界值
//        Comparable key = a[lo];
//        //定义两个索引
//        int left = lo;
//        int right = hi+1;
//
//        while(true){
//            //从右往左扫描，移动right索引，直到找到比分界值key小的元素，跳出循环
//            while(less(key,a[--right])){
//                if (right==lo) break;
//            }
//            //左边同理
//            while (less(a[++left],key)){
//                if (left==hi) break;
//            }
//            //若left>right则证明元素扫描完毕，结束循环，否则交换元素
//            if (left>=right){
//                break;
//            }else{
//                exch(a,left,right);
//            }
//        }
//        //将分界值放到最终位置
//        exch(a,lo,right);
//
//        return right;
//    }

    public int[] quickSort(int[] a,int first,int last){
        if(first<last){                //至少两个位置
            int pivotIndex=partition1(a,first,last);  //定义pivotIndex中间位置。partition是检索这个方法
            quickSort(a,first,pivotIndex-1);              //排序左半边
            quickSort(a,pivotIndex+1,last);               //排序右半边
        }
        return a;
    }
    public int partition1(int[] a,int left,int right){//对数组A下标从first到last中选一个主元，确定其位置，左边小于，右边大于。

        int pivot=a[left];//先定义区间数组第一个元素为主元
        int i=left;   //定义最低的索引low是first+1。比主元大一位
        int j=right;     //定义最高的索引high是last
        while(i<j){   //当low小于high的位置时，执行以下循环
            while(a[j]>pivot&&i<j){//当high的索引上的值比主元大时，且索引大于low时
                j--;                      //寻找比主元小的值的位置索引
            }
            while(a[i]<=pivot&&i<j){//当low的索引上的值比主元小时，索引小于high时
                i++;                       //寻找比主元大的值的位置索引。
            }

            if(i<j){   //交换low和high的值
                int t=a[i];
                a[i]=a[j];
                a[j]=t;
            }
        }

        a[left]=a[j];
        a[j]=pivot;
        return j;
    }
}

